package com.ljx.DaJieJieShe;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author 李加喜
 * @Package com.ljx.DaJieJieShe
 * @date 2021-11-13 9:35
 */
// 打家劫舍1
public class MaxDaJia {
    public static void main(String[] args) {
        MaxDaJia maxDaJia = new MaxDaJia();
        int[] num={1,2,3,1};
        System.out.println(maxDaJia.rob1(num));
    }
    public int rob(int[] nums) {
        int n=nums.length;
        // 初始化备忘录
        int[] memo=new int[n];
        Arrays.fill(memo,-1);
        return dp(nums,0,memo);
    }
    public int rob1(int[] nums) {
        int n = nums.length;
        // dp[i] = x 表示：
        // 从第 i 间房子开始抢劫，最多能抢到的钱为 x
        // base case: dp[n] = 0
        int[] dp = new int[n + 2];
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2]);
        }
        return dp[0];

    }
    /**
     * 表示i房间最多能够抢到的前
     * @param nums 房子数组
     * @param i 第i哥房间
     * @return
     */
    private int dp(int[] nums, int i,int[] memo) {
        if (nums.length==0){
            return 0;
        }
        if (i>=nums.length){
            return 0;
        }
        if (memo[i]!=-1){
            // 已经计算过的就不需要在进行计算了
            return memo[i];
        }
        // 当前不强 强下一个 or 当前抢 抢的是各一个的房间
        int res=Math.max(dp(nums,i+1,memo),nums[i]+dp(nums,i+2,memo));
        memo[i]=res;
        return res;
    }
}
